package com.wx.algorithm.sort;

import com.wx.ArrayUtils;

/**
 * @ClassName SimpleBarrelSort
 * @Author wx
 * @Description 代码简化版桶排序
 *  时间复杂度(n)
 *  空间复杂度(max)
 * @Date 2020-03-29-13:04
 */
public class SimpleBarrelSort {


    public static void sort(int[] array) {
        if (ArrayUtils.arrayValidation(array)){
            return;
        }

        int max = 0;
        //获取数组最大值
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max,array[i]);
        }

        int[] temp = new int[max + 1];

        for (int i = 0; i < array.length; i++) {
            temp[array[i]]++;
        }

        int j = 0;
        for (int i = 0; i < temp.length; i++) {
            while (temp[i] -- > 0){
                array[j++] = i;
            }
        }
    }
    
    public static void main(String[] agrs){
      ArrayUtils.logarithmicRun(10000,20,10,SimpleBarrelSort::sort);
    }
}
